package com.ting.test.algorithms.大厂刷题班;

/**
 * 给定一个数组 每个元素表示能够跳跃的步数
 * 求跳到最末尾最少需要几步
 */
public class 跳跃游戏 {

    public static void main(String[] args) {
        int [] arr=new int[]{21,3,4,6,7,8,3,21};
        int count=procss(arr);
        System.out.println(count);

    }

    private static int procss(int[] arr) {
        if(arr==null||arr.length==0){
            return 0;
        }

        int step=0;//表示当前跳的步数
        int cur=0;//表示当前在step步内能够跳到的最远的位置
        int next=arr[0];

        for(int i=0;i< arr.length;i++){
            if(i>cur){//如果当前位置超过了cur能够到达的最远位置，step+1；
                step++;
                cur=next;
            }
            next=Math.max(i+arr[i],next);//chubei
        }
        return step;
    }
}
